package com.gxc.sort;

import com.gxc.randomArray.generateRandomArray;

/**
 * 快排
 */
public class quick {

    public static void main(String[] args) {
        int[] arr = generateRandomArray.generateArray(20, 30);

        generateRandomArray.sout(arr);

        //归并排序
        quickSuanfa(arr, 0, arr.length-1);

        System.out.println("=======排序后=====");

        generateRandomArray.sout(arr);
    }

    private static void quickSuanfa(int[] arr, int l, int r) {
        if (l<r) {
            generateRandomArray.swap(arr, l+(int) (Math.random()*(r-l+1)) , r);

            int stand = arr[r];
            //小于范围
            int less = l-1;
            //大于范围
            int greater = r;
            /*int L = l;
            while (L<greater) {
                if (arr[L]<stand) {
                    generateRandomArray.swap(arr, ++less, L++);
                } else if (arr[L]>stand) {
                    generateRandomArray.swap(arr, --greater, L);
                } else {
                    L++;
                }
            }*/
            for (int i = l; i < greater; i++) {
                if (arr[i]<stand) {
                    generateRandomArray.swap(arr, i, ++less);
                } else if (arr[i]==stand) {
                } else {
                    generateRandomArray.swap(arr, i, --greater);
                    i--;
                }
            }
            generateRandomArray.swap(arr, greater, r);
            quickSuanfa(arr, l, less);
            quickSuanfa(arr, greater+1, r);
        }

    }


}
